package Validate_Binary_Search_Tree
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
/*
验证二叉树是否有效
开始的思路：我们可以判断当前节点和左右节点值的大小，然后进行递归，但是问题是[5,1,4,null,null,3,6]，如果出现这样的链表，
就会导致没有办法判断3比根节点的5小，所以此方法不行。
第二种方法，
也是进行递归，但是区别在于，传参不同，通过传参进行缩小取值范围。
每一次通过传参，缩小取值范围，如果节点为空，直接返回true
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
func IsValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return find(root , -(1 << 63) , (1 << 63) - 1)
}


func find (node *TreeNode , lower , upper int) bool {
	if node == nil {
		return true
	}
	if node.Val <= lower || node.Val >= upper {
		return false
	}
	return find(node.Left , lower , node.Val) && find(node.Right , node.Val , upper)
}